/*
 * @lc app=leetcode.cn id=104 lang=cpp
 *
 * [104] 二叉树的最大深度
 *
 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/
 *
 * algorithms
 * Easy (76.93%)
 * Likes:    1184
 * Dislikes: 0
 * Total Accepted:    682.4K
 * Total Submissions: 887K
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * 给定一个二叉树，找出其最大深度。
 * 
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 
 * 说明: 叶子节点是指没有子节点的节点。
 * 
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * 
 * ⁠   3
 * ⁠  / \
 * ⁠ 9  20
 * ⁠   /  \
 * ⁠  15   7
 * 
 * 返回它的最大深度 3 。
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // int maxDepth(TreeNode* root) {
    //     //层序遍历-广度优先遍历
    //     queue<TreeNode*> que;
    //     TreeNode* cur = root;
    //     if(cur == NULL) return 0;
    //     que.push(cur);
    //     int res = 0;

    //     while(!que.empty()){
    //         int size = que.size();
    //         for(int i = 0; i < size; i++){
    //             cur = que.front();
    //             que.pop();
    //             if(cur->left) que.push(cur->left);
    //             if(cur->right) que.push(cur->right);
    //         }
    //         res++;
    //     }
    //     return res;
    // }


    // //清晰解释
    // int getDepth(TreeNode* node) {
    //     if(node == NULL) return 0;
    //     int leftDepth = getDepth(node->left);
    //     int rightDepth = getDepth(node->right);

    //     int depth = 1 + max(leftDepth, rightDepth);
    //     return depth;
    // }
    // int maxDepth(TreeNode* root) {
    //     //后序遍历-左右中-递归-深度优先遍历
    //     return getDepth(root);       
    // } 


    // //便捷写法1
    // int maxDepth(TreeNode* root) {
    //     //后序遍历-左右中-递归-深度优先遍历
    //      if(root == NULL) return 0;
    //     int leftDepth = maxDepth(root->left);
    //     int rightDepth = maxDepth(root->right);

    //     int depth = 1 + max(leftDepth, rightDepth);
    //     return depth;       
    // }   
    //便捷写法2
    // int maxDepth(TreeNode* root) {
    //     //后序遍历-左右中-递归-深度优先遍历
    //     if(root == NULL) return 0;
    //     return 1 + max(maxDepth(root->left),  maxDepth(root->right));;       
    // }  
  

  
    // //前序遍历-中左右

    // 为什么 完事儿之后需要depth--？？？？？
    // 这里的回溯指的是，左边的节点走完了，左孩子已经遍历完了，已经知道了左边的最大深度
    // 此时 ,!!! 问题就在这里，需要depth--，目的是回到左孩子的父节点的深度，
    // 然后 从此深度，继续往右孩子那边继续探索，
    // 所以，继续探索深度的出发点应该是父节点，而不是左孩子几点的深度情况下，继续探索

    // int res = 0;
    // void getDepth(TreeNode* node, int depth){

    //     res = res > depth ? res : depth; //中
    //     if(node->left == NULL && node->right == NULL) return;

    //     if(node->left){ //左
    //         depth++; //深度加1
    //         getDepth(node->left, depth);
    //         depth--; //回溯，深度减1
    //     }

    //     if(node->right){ //右
    //         depth++; //深度加1
    //         getDepth(node->right, depth);
    //         depth--; //回溯，深度减1
    //     }

    //     return;

    // }

    // int maxDepth(TreeNode* node) {
    //     if(node == NULL) return 0;
    //     getDepth(node, 1);
    //     return res;
    // }



    int res = 0;
    int maxDepth(TreeNode* node) {
        if(node == NULL) return 0;
        getDepth(node, 1);
        return res;
    }
    void getDepth(TreeNode* node, int depth){

        res = res > depth ? res : depth;

        if(node->left == NULL && node->right == NULL) return;

        if(node->left){ //左
            //回溯隐匿于函数参数中，是因为，参数仅仅是复制，不参与改变变量
            //完成调用后，又恢复了原来的值
            getDepth(node->left, depth + 1);
        }

        if(node->right){ //右
            getDepth(node->right, depth + 1);
        }

        return;

    }

};
// @lc code=end

